package _0_5_编辑距离

/*
https://leetcode.cn/problems/longest-palindromic-subsequence/

516.最长回文子序列
力扣题目链接(opens new window)
给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

示例 1: 输入: "bbbab" 输出: 4 一个可能的最长回文子序列为 "bbbb"。
示例 2: 输入:"cbbd" 输出: 2 一个可能的最长回文子序列为 "bb"。

提示：
1 <= s.length <= 1000
s 只包含小写英文字母
*/

func longestPalindromeSubseq(s string) int {
	n := len(s) //获取字符串长度

	dp := make([][]int, n) //声明dp数组
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
		dp[i][i] = 1 //dp[i][i]: i为起点,i为终点, 构成长度为1的回文子序列
	}

	for i := n - 1; i >= 0; i-- { //从末尾开始遍历
		for j := i + 1; j < n; j++ { //从i+1, 遍历到字符串末尾
			if s[i] == s[j] { //如果i,j对应字符相等, 那么dp[i][j]等于中间的段最长回文子序列长度+2
				dp[i][j] = dp[i+1][j-1] + 2
			} else { //如果不相等, 那么直接取值左右两端能够构成更大子序列长度的dp值
				dp[i][j] = max(dp[i][j-1], dp[i+1][j])
			}
		}
	}

	//返回以0为开始, n-1下标范围内, 能够构成的最长回文子序列长度
	return dp[0][n-1]
}
